package com.tgy.programmer_code_interview_guide._02_linkedList;

/**
 * @Author: tgy
 * @Date: 1/25/21 9:24 AM
 */
public class _06_约瑟夫问题_01 {

    public static Node josephusProblem(Node node, int killNum) {

        if (node == null || node.next == null || killNum <= 0) {

            return node;
        }

        int len = 1;

        Node tmpNode = node;
        while (tmpNode.next != node) {

            len++;
            tmpNode = tmpNode.next;
        }

        /**
         *
         * f(1) = 0
         * f(n) = (f(n - 1) + m) % n
         */
        int removeIndex = 0;
        for (int i = 2; i <= len; i++) {

            removeIndex = (removeIndex + killNum) % i;
        }


        int index = 0;
        tmpNode = node;
        while (index != removeIndex) {

            index++;
            tmpNode = tmpNode.next;
        }


        return tmpNode;
    }

      public static void main(String[] args) {

          Node root = new Node(1);
          root.next = new Node(2);
          root.next.next = new Node(3);
          root.next.next.next = new Node(4);
          root.next.next.next.next = new Node(5);
          root.next.next.next.next.next = root;

          Node node = josephusProblem(root, 4);
            System.out.println(node.val);
      }
}
